#include <stdlib.h>
#include <stdio.h>

#include "./TDA_ArbolBinarioBusqueda.h"

//==============================================================================

#define FALLO 0
#define OK 1
#define MEM_INSUF 2

struct Nodo{
  
  tDato dato;
  struct Nodo *izq
            ,  *der;  

};

typedef struct Nodo* tNodo;

struct ArbolBinarioBusqueda{
  
  tNodo raiz;
  
  tFcnOrdenPrecedenciaDato fcnOrdenPrecedenciaDato;
  tFcnDestructorDato fcnDestructorDatos;
  
};

struct IteradorEnOrden {

  tNodo cursor;
  struct ArbolBinarioBusqueda* arbol;

};

//==============================================================================

// Validaciones

int validarParametrosCrearArbol (tArbolBinarioBusqueda* pArbol
                               , tFcnDestructorDato pDestructorDato
                               , tFcnOrdenPrecedenciaDato pOrdenPrecedencia);

//==============================================================================

// Funciones auxiliares.

int fcnDestructorDatoDummy (tDato pDato);

tNodo crearNodo (tDato pDato);

void destruirNodo (tNodo pNodo);

tNodo buscarNodoPorDato (tDato pDato
                       , tNodo pNodo
                       , tFcnOrdenPrecedenciaDato pOrdenPrecedencia);

tNodo seleccionarNodoPadre (tDato pDato
                          , tNodo raiz
                          , tFcnOrdenPrecedenciaDato pOrdenPrecedencia);

tNodo obtenerNodoPadrePorArbol (tArbolBinarioBusqueda pArbol, tNodo pNodo);

tNodo obtenerNodoPadrePorIteradorEnOrden (tIteradorEnOrden pIterador, tNodo pNodo);

tNodo obtenerNodoPadrePorRaiz (tNodo pRaiz, tNodo pNodo, tFcnOrdenPrecedenciaDato pFcnOrdenPrecedencia);

void removerNodo (tArbolBinarioBusqueda pArbol, tNodo pNodo);

//==============================================================================
//==============================================================================
//==============================================================================

// Definicion de funciones de TDA.

//------------------------------------------------------------------------------

int crearArbol (tArbolBinarioBusqueda* pArbol
              , tFcnDestructorDato pDestructorDato
              , tFcnOrdenPrecedenciaDato pOrdenPrecedencia)
{

  int estado = validarParametrosCrearArbol (pArbol, pDestructorDato, pOrdenPrecedencia);
  
  if (OK == estado)
  {
    // Reservo memoria para el arbol.
    //
    tArbolBinarioBusqueda arbol = (tArbolBinarioBusqueda) malloc (sizeof (struct ArbolBinarioBusqueda));
    
    if (arbol)
    {
      arbol->raiz = NULL;            
      arbol->fcnOrdenPrecedenciaDato = pOrdenPrecedencia;
            
      if (NULL == pDestructorDato)
        // El usuario se reserva la potestad de eliminar el dato de los nodos.
        // Se utiliza la funcion de elminar nodo Dummy.
        arbol->fcnDestructorDatos = &fcnDestructorDatoDummy;
      else
        // El usuario delega en el arbol la potestad de eliminar el dato del nodo.
        arbol->fcnDestructorDatos = pDestructorDato;

      (*pArbol) = arbol;
    }
    else
      estado = MEM_INSUF;
  }
  return estado;
}

//------------------------------------------------------------------------------

void destruirEstructuraArbol (tNodo pNodo, tFcnDestructorDato pFcnDestructorDato)
{
    if (pNodo)
    {
      destruirEstructuraArbol(pNodo->izq, pFcnDestructorDato);
      destruirEstructuraArbol(pNodo->der, pFcnDestructorDato);
      pFcnDestructorDato(pNodo->dato);
      
      destruirNodo (pNodo);
      
    }
}

void destruirArbol (tArbolBinarioBusqueda pArbol){

  if (NULL != pArbol)
    destruirEstructuraArbol(pArbol->raiz, pArbol->fcnDestructorDatos);

}

//------------------------------------------------------------------------------

tDato agregarDatoArbol (tArbolBinarioBusqueda pArbol, tDato pDato) {
  
  tNodo nodo = buscarNodoPorDato(pDato, pArbol->raiz, pArbol->fcnOrdenPrecedenciaDato);
  
  if (NULL == nodo)
  {
    // El dato no existe en la estructura. Identifico el nodo que seria raiz del
    // nodo que contendra el dato.
    
    nodo = seleccionarNodoPadre(pDato, pArbol->raiz, pArbol->fcnOrdenPrecedenciaDato);
    
    if (nodo)
    {
      
      
        // Evaluo si el dato debe ir a la derecha/izquierda del nodo.
        switch(pArbol->fcnOrdenPrecedenciaDato(pDato, nodo->dato))
        {
          case -1: // Debe ir a la izquierda.
            nodo->izq = crearNodo(pDato);
            break;
            
          case 1: // Debe ir a la derecha.
            nodo->der = crearNodo(pDato);
            break;
        }
    }
    else
      pArbol->raiz = crearNodo (pDato);      // El nodo deberia ser un nodo raiz.
  }
  else
  {
    // Exite el dato en el arbol segun el criterio de comparacion.  
    // Actualizo el dato existente con el dato suministrado.
    
    pArbol->fcnDestructorDatos (nodo->dato);
    nodo->dato = pDato;
  }
  
  return pDato;
  
}

//------------------------------------------------------------------------------

void removerDatoArbol (tArbolBinarioBusqueda pArbol, tDato pDato) {

  tNodo nodo = buscarNodoPorDato (pDato, pArbol->raiz, pArbol->fcnOrdenPrecedenciaDato);
  
  if (nodo)
  {

    // Hay un nodo que eliminar.
    
    // Identifico de donde hay que referenciar la subestrucutra una vez removido
    // el nodo.
    tNodo padre, *referencia;
    
    referencia = NULL;
    padre = obtenerNodoPadrePorArbol(pArbol, nodo);
    
    if (NULL == padre)
      referencia = &(pArbol->raiz);
    else
    {
      switch (pArbol->fcnOrdenPrecedenciaDato(pDato, padre->dato))
      {
        case -1:
          referencia = &(padre->izq);
          break;
          
        case 1:
          referencia = &(padre->der);
          break;
      }
    }
    
    // Remuevo el nodo de la estructura preservando el orden de los datos.

    if (NULL == nodo->izq)
      *referencia = nodo->der;
    
    else if (NULL == nodo->der)
      *referencia = nodo->izq;
    
    else 
    {
      padre = nodo;
      tNodo cursor = nodo->izq;
      while (NULL != cursor->der)
      {
        padre = cursor;
        cursor = cursor->der;
      }
      
      nodo->dato = cursor->dato;
      
      if (padre == nodo)
        padre->izq = cursor->izq;
      else
        padre->der = cursor->der;
      nodo = cursor;
      
    }

    destruirNodo(nodo);
  }
  
}

//------------------------------------------------------------------------------
/*
 * obtenerIteradorEnOrden: construye un iterador que permite recorrer el arbol en orden
 * pre:
 *  el arbol debe haber sido definido previamente mediante la funcion crearArbol.
 * pos:
 *  El iterador apunta a la posicion previa al primer dato de la iteracion.
 * */
tIteradorEnOrden obtenerIteradorEnOrden (tArbolBinarioBusqueda pArbol){
  
  tIteradorEnOrden iterador = malloc (sizeof(struct IteradorEnOrden));
  
  if (iterador)
  {
      iterador->cursor = NULL;
      iterador->arbol = pArbol;
  }
  
  return iterador;
  
}

/*
 * liberarIteradorEnOrden: libera los recursos que este utilizando el iterador.
 * pre:
 *  El iterador debe haber sido iniciado mediante obtenerIteradorEnOrden.
 * pos:
 *  El iterador queda indefinido.
 * */
void liberarIteradorEnOrden (tIteradorEnOrden pIterador){
  
  if (pIterador)
  {
    pIterador->cursor = NULL;
    pIterador->arbol = NULL;

  }
}

/*
 * iteradorEnOrdenMoverInicio: 
 *  configura el iterador para que apunte a la posicion previa al primer nodo de 
 *  iteracion.
 * pre:
 *  El iterador debe haber sido inicializado mediante obtenerIteradorEnOrden.
 * pos:
 *  El iterador se encuentra configurado para iterar desde el inicio de la coleccion
 *  segun el recorrido En Orden. 
 * ret:
 *  Retorna 0 en caso de que la coleccion se encuentre vacia, 1 en caso de que el
 *  iterador se encuentre listo para iterar.
 * */
int iteradorEnOrdenMoverInicio (tIteradorEnOrden pIterador)
{
  int val = 0;  // La coleccion esta vacia hasta que se demuetre lo contrario.
  
  if (pIterador)
  {
    if (NULL != pIterador->arbol->raiz) val = 1; // la coleccion contiene datos.
    pIterador->cursor = NULL; 
  }
  
  return val;
}

/*
 * iteradorEnOrdenMoverSiguiente:
 *  posiciona al iterador en el siguiente dato en la coleccion. Al ejecutarse
 *  imediatamente despues de la inicializacion del iterador, el iterador apunta
 *  al primer dato contenido en la coleccion segun el recorido de iteracion
 *  "En Orden".
 * pre:
 *  El iterador debe haber sido inicializado mediante obtenerIteradorEnOrden.
 * pos:
 *  El iterador se posciona en el dato siguiente tomando como referencia la
 *  la posicion actual del iterador.
 * ret:
 *  Retorna 1 en caso de que el iterador se encuentre apuntando a un dato tras
 *  la operacion.  Retorna 0 en caso de haber llegado al fin de la coleccion.
 * */
int iteradorEnOrdenMoverSiguiente (tIteradorEnOrden pIterador){
  
  int val = 0; // Fin de la coleccion hasta que se demuestre lo contrario.
  
  if (pIterador)
  {
    if (NULL == pIterador->arbol->raiz)
      
      // El arbol se encuentra vacio.
      pIterador->cursor = NULL;
    
    else if (NULL == pIterador->cursor)
    {
        // Me encuentro en el inicio/fin de la coleccion.  Posiciono el cursor
        // en el primer nodo segun recorrido "En Orden".
      
      pIterador->cursor = pIterador->arbol->raiz;
      
      while (NULL != pIterador->cursor->izq)
        pIterador->cursor = pIterador->cursor->izq;
      
    } 
    else if (NULL != pIterador->cursor->der)
    {
      pIterador->cursor = pIterador->cursor->der;
      while (NULL != pIterador->cursor->izq)
        pIterador->cursor = pIterador->cursor->izq;
    }
    else 
    {
      tNodo padre = obtenerNodoPadrePorIteradorEnOrden (pIterador, pIterador->cursor);
      
      if (NULL != padre)
      {
        if (pIterador->cursor == padre->izq)
          pIterador->cursor = padre;
        else
          pIterador->cursor = obtenerNodoPadrePorIteradorEnOrden (pIterador, padre);
      }
      else
        pIterador->cursor = NULL;
    }
      
    if (NULL != pIterador->cursor)
      val = 1;
  }

  return val;

}

/*
 * iteradorEnOrdenObtenerActual:
 *  obtiene el dato del arbol al que hace referencia el iterador segun el estado
 *  de iteracion actual.
 * pre:
 *  El iterador debe haber sido inicializado mediante obtenerIteradorEnOrden.
 * ret:
 *  el dato contenido en el arbol al que hace referencia el iterador segun su
 *  posicion actual.  Retorna NULL en caso de que el arbol se encuentre vacio,
 *  se encuentre iniciado para iteracion o se halla llegado al final de la coleccion.
 * */
tDato iteradorEnOrdenObtenerActual (tIteradorEnOrden pIterador){

  if (pIterador)
    return pIterador->cursor->dato;
  
}


//==============================================================================
//==============================================================================
//==============================================================================

int validarParametrosCrearArbol (tArbolBinarioBusqueda* pArbol
                               , tFcnDestructorDato pDestructorDato
                               , tFcnOrdenPrecedenciaDato pOrdenPrecedencia)
{
  return OK;
}

//------------------------------------------------------------------------------

tNodo crearNodo (tDato pDato) {
  
  tNodo nodo = (tNodo) malloc(sizeof(struct Nodo));
  
  if (nodo)
  {
    nodo->dato = pDato;
    nodo->izq = NULL;
    nodo->der = NULL;
  }
  
  return nodo;
  
}

//------------------------------------------------------------------------------

void destruirNodo (tNodo pNodo) {
  
  if (NULL != pNodo)
    free (pNodo);
  
}

//------------------------------------------------------------------------------

tNodo seleccionarNodoPadre (tDato pDato
                          , tNodo raiz
                          , tFcnOrdenPrecedenciaDato pOrdenPrecedencia) 
{
  tNodo nodo = NULL;
  int terminar = 0;
  
  while (NULL != raiz && !terminar)
  {
    switch(pOrdenPrecedencia(pDato, raiz->dato))
    {
      case -1:
        nodo = raiz;
        raiz = raiz->izq;
        break;
      
      case 0:
        terminar = 1;
        break;
        
      case 1:
        nodo = raiz;
        raiz = raiz->der;
        break;          
    }
  } // while
  
  return nodo;
}

//------------------------------------------------------------------------------

tNodo buscarNodoPorDato (tDato pDato
                       , tNodo pNodo
                       , tFcnOrdenPrecedenciaDato pOrdenPrecedencia) 

{

  if (NULL != pNodo)
  {
      switch ((*pOrdenPrecedencia)(pDato,pNodo->dato))
      {
        case -1:
          return buscarNodoPorDato (pDato, pNodo->izq, pOrdenPrecedencia);

        case 0:
          return pNodo;
        
        case 1:
          return buscarNodoPorDato(pDato, pNodo->der, pOrdenPrecedencia);
      }
  }
  
  return NULL;
  
}

//------------------------------------------------------------------------------

tNodo obtenerNodoPadrePorArbol (tArbolBinarioBusqueda pArbol, tNodo pNodo){
  
  return obtenerNodoPadrePorRaiz(pArbol->raiz, pNodo, pArbol->fcnOrdenPrecedenciaDato);
}

tNodo obtenerNodoPadrePorIteradorEnOrden (tIteradorEnOrden pIterador, tNodo pNodo){

  return obtenerNodoPadrePorRaiz(pIterador->arbol->raiz, pNodo, pIterador->arbol->fcnOrdenPrecedenciaDato);
  
}

//------------------------------------------------------------------------------

// Si el nodo no pertenece  a la coleccion el el resultado es indefinido.

tNodo obtenerNodoPadrePorRaiz (tNodo pRaiz, tNodo pNodo, tFcnOrdenPrecedenciaDato pFcnOrdenPrecedencia){
  
  tNodo padre = NULL
      , cursor = pRaiz;
      
  int encontrado = 0;
  
  while (!encontrado && NULL != cursor)
  {
    switch (pFcnOrdenPrecedencia(pNodo->dato, cursor->dato))
    {
      case -1:
          padre = cursor;
          cursor = cursor->izq;
        break;
        
      case 0:
        encontrado = 1;
        break;
        
      case 1:
        padre = cursor;
        cursor = cursor->der;
        break;
    }
    
  }
  
  return padre;
  
}

//------------------------------------------------------------------------------

int fcnDestructorDatoDummy (tDato pDato){/*dummy*/}

